#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/13 9:39
# @USER    : Shengji He
# @File    : IntersectionTwoArrays2.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List
from collections import Counter


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        Given two arrays, write a function to compute their intersection.

        Example 1:
            Input: nums1 = [1,2,2,1], nums2 = [2,2]

            Output: [2,2]

        Example 2:
            Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

            Output: [4,9]

        Note:
            - Each element in the result should appear as many times as it shows in both arrays.
            - The result can be in any order.

        Follow up:
            - What if the given array is already sorted? How would you optimize your algorithm?
            - What if nums1's size is small compared to nums2's size? Which algorithm is better?
            - What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all
            elements into the memory at once?

        :param nums1:
        :param nums2:
        :return:
        """
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)
        ncount = Counter(nums1)
        intersection = list()
        for num in nums2:
            if ncount[num] > 0:
                intersection.append(num)
                ncount[num] -= 1
        return intersection


if __name__ == '__main__':
    # num1 = [1, 2, 2, 1]
    # num2 = [2, 2]
    num1 = [4, 9, 5]
    num2 = [9, 4, 9, 8, 4]
    S = Solution()
    print(S.intersect(num1, num2))
    print('done')
